home *** CD-ROM | disk | FTP | other *** search
/ MACD 5 / MACD 5.bin / workbench / tools / czesc_2 / ispell-3.3ljr / ispell / regex.c < prev    next >
C/C++ Source or Header  |  1992-09-22  |  19KB  |  893 lines
  1. /*
  2.  * regex - Regular expression pattern matching
  3.  *         and replacement
  4.  *
  5.  *
  6.  * By:  Ozan S. Yigit (oz)
  7.  *      Dept. of Computer Science
  8.  *      York University
  9.  *
  10.  *
  11.  * These routines are the PUBLIC DOMAIN equivalents
  12.  * of regex routines as found in 4.nBSD UN*X, with minor
  13.  * extensions.
  14.  *
  15.  * These routines are derived from various implementations
  16.  * found in software tools books, and Conroy's grep. They
  17.  * are NOT derived from licensed/restricted software.
  18.  * For more interesting/academic/complicated implementations,
  19.  * see Henry Spencer's regexp routines, or GNU Emacs pattern
  20.  * matching module.
  21.  *
  22.  * Routines:
  23.  *      re_comp:        compile a regular expression into
  24.  *                      a DFA.
  25.  *
  26.  *            char *re_comp(s)
  27.  *            char *s;
  28.  *
  29.  *      re_exec:        execute the DFA to match a pattern.
  30.  *
  31.  *            int re_exec(s)
  32.  *            char *s;
  33.  *
  34.  *    re_modw        change re_exec's understanding of what
  35.  *            a "word" looks like (for \< and \>)
  36.  *            by adding into the hidden word-character
  37.  *            table.
  38.  *
  39.  *            void re_modw(s)
  40.  *            char *s;
  41.  *
  42.  *      re_subs:    substitute the matched portions in
  43.  *                  a new string.
  44.  *
  45.  *            int re_subs(src, dst)
  46.  *            char *src;
  47.  *            char *dst;
  48.  *
  49.  *    re_fail:    failure routine for re_exec.
  50.  *
  51.  *            void re_fail(msg, op)
  52.  *            char *msg;
  53.  *            char op;
  54.  *
  55.  * Regular Expressions:
  56.  *
  57.  *      [1]     char    matches itself, unless it is a special
  58.  *                      character (metachar): . \ [ ] * + ^ $
  59.  *
  60.  *      [2]     .       matches any character.
  61.  *
  62.  *      [3]     \       matches the character following it, except
  63.  *            when followed by a left or right round bracket,
  64.  *            a digit 1 to 9 or a left or right angle bracket.
  65.  *            (see [7], [8] and [9])
  66.  *            It is used as an escape character for all
  67.  *            other meta-characters, and itself. When used
  68.  *            in a set ([4]), it is treated as an ordinary
  69.  *            character.
  70.  *
  71.  *      [4]     [set]   matches one of the characters in the set.
  72.  *                      If the first character in the set is "^",
  73.  *                      it matches a character NOT in the set. A
  74.  *                      shorthand S-E is used to specify a set of
  75.  *                      characters S upto E, inclusive. The special
  76.  *                      characters "]" and "-" have no special
  77.  *                      meaning if they appear as the first chars
  78.  *                      in the set.
  79.  *                      examples:        match:
  80.  *
  81.  *                              [a-z]    any lowercase alpha
  82.  *
  83.  *                              [^]-]    any char except ] and -
  84.  *
  85.  *                              [^A-Z]   any char except uppercase
  86.  *                                       alpha
  87.  *
  88.  *                              [a-zA-Z] any alpha
  89.  *
  90.  *      [5]     *       any regular expression form [1] to [4], followed by
  91.  *                      closure char (*) matches zero or more matches of
  92.  *                      that form.
  93.  *
  94.  *      [6]     +       same as [5], except it matches one or more.
  95.  *
  96.  *      [7]             a regular expression in the form [1] to [10], enclosed
  97.  *                      as \(form\) matches what form matches. The enclosure
  98.  *                      creates a set of tags, used for [8] and for
  99.  *                      pattern substution. The tagged forms are numbered
  100.  *            starting from 1.
  101.  *
  102.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  103.  *                      previously tagged regular expression ([7]) matched.
  104.  *
  105.  *    [9]    \<    a regular expression starting with a \< construct
  106.  *        \>    and/or ending with a \> construct, restricts the
  107.  *            pattern matching to the beginning of a word, and/or
  108.  *            the end of a word. A word is defined to be a character
  109.  *            string beginning and/or ending with the characters
  110.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  111.  *            followed by any character outside those mentioned.
  112.  *
  113.  *      [10]            a composite regular expression xy where x and y
  114.  *                      are in the form [1] to [10] matches the longest
  115.  *                      match of x followed by a match for y.
  116.  *
  117.  *      [11]    ^    a regular expression starting with a ^ character
  118.  *        $    and/or ending with a $ character, restricts the
  119.  *                      pattern matching to the beginning of the line,
  120.  *                      or the end of line. [anchors] Elsewhere in the
  121.  *            pattern, ^ and $ are treated as ordinary characters.
  122.  *
  123.  *
  124.  * Acknowledgements:
  125.  *
  126.  *    HCR's Hugh Redelmeier has been most helpful in various
  127.  *    stages of development. He convinced me to include BOW
  128.  *    and EOW constructs, originally invented by Rob Pike at
  129.  *    the University of Toronto.
  130.  *
  131.  * References:
  132.  *              Software tools            Kernighan & Plauger
  133.  *              Software tools in Pascal        Kernighan & Plauger
  134.  *              Grep [rsx-11 C dist]            David Conroy
  135.  *        ed - text editor        Un*x Programmer's Manual
  136.  *        Advanced editing on Un*x    B. W. Kernighan
  137.  *        RegExp routines            Henry Spencer
  138.  *
  139.  * Notes:
  140.  *
  141.  *    This implementation uses a bit-set representation for character
  142.  *    classes for speed and compactness. Each character is represented
  143.  *    by one bit in a 128-bit block. Thus, CCL or NCL always takes a
  144.  *    constant 16 bytes in the internal dfa, and re_exec does a single
  145.  *    bit comparison to locate the character in the set.
  146.  *
  147.  * Examples:
  148.  *
  149.  *    pattern:    foo*.*
  150.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  151.  *    matches:    fo foo fooo foobar fobar foxx ...
  152.  *
  153.  *    pattern:    fo[ob]a[rz]
  154.  *    compile:    CHR f CHR o CCL 2 o b CHR a CCL bitset END
  155.  *    matches:    fobar fooar fobaz fooaz
  156.  *
  157.  *    pattern:    foo\\+
  158.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  159.  *    matches:    foo\ foo\\ foo\\\  ...
  160.  *
  161.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  162.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  163.  *    matches:    foo1foo foo2foo foo3foo
  164.  *
  165.  *    pattern:    \(fo.*\)-\1
  166.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  167.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  168.  *
  169.  */
  170.  
  171. #include <stdio.h>
  172. #include "ispell.h"
  173.  
  174. /*
  175.  * re_fail:
  176.  *    internal error handler for re_exec.
  177.  *
  178.  *    should probably do something like a
  179.  *    longjump to recover gracefully.
  180.  */
  181. void re_fail (char *s, int c)
  182. {
  183.   fprintf (stderr, "regex: %s [opcode %o]\n", s, c);
  184. }
  185.  
  186. #define MAXDFA  1024
  187. #define MAXTAG  10
  188.  
  189. #define OKP     1
  190. #define NOP     0
  191.  
  192. #define CHR     1
  193. #define ANY     2
  194. #define CCL     3
  195. #define NCL     4
  196. #define BOL     5
  197. #define EOL     6
  198. #define BOT     7
  199. #define EOT     8
  200. #define BOW    9
  201. #define EOW    10
  202. #define REF     11
  203. #define CLO     12
  204.  
  205. #define END     0
  206.  
  207. /*
  208.  * The following defines are not meant
  209.  * to be changeable. They are for readibility
  210.  * only.
  211.  *
  212.  */
  213. #define MAXCHR    128
  214. #define CHRBIT    8
  215. #define BITBLK    MAXCHR/CHRBIT
  216. #define BLKIND    0170
  217. #define BITIND    07
  218.  
  219. #define ASCIIB    0177
  220.  
  221. static int tagstk[MAXTAG];    /* subpat tag stack..*/
  222. static char dfa[MAXDFA];    /* automaton..       */
  223. static int sta = NOP;        /* status of lastpat */
  224.  
  225. static char bittab[BITBLK];    /* bit table for CCL */
  226.  
  227. static void chset (int c)
  228. {
  229.   bittab[((c) & BLKIND) >> 3] |= 1 << ((c) & BITIND);
  230. }
  231.  
  232. #define badpat(x)    return(*dfa = END, x)
  233. #define store(x)    *mp++ = x
  234.  
  235. char *re_comp (char *pat)
  236. {
  237.   register char *p;        /* pattern pointer   */
  238.   register char *mp = dfa;    /* dfa pointer       */
  239.   register char *lp;        /* saved pointer..   */
  240.   register char *sp = dfa;    /* another one..     */
  241.  
  242.   register int tagi = 0;    /* tag stack index   */
  243.   register int tagc = 1;    /* actual tag count  */
  244.  
  245.   register int n;
  246.   int c1, c2;
  247.  
  248.   if (!pat || !*pat)
  249.     if (sta)
  250.       return (0);
  251.     else
  252.       badpat ("No previous regular expression");
  253.   sta = NOP;
  254.  
  255.   for (p = pat; *p; p++)
  256.     {
  257.       lp = mp;
  258.       switch (*p)
  259.     {
  260.  
  261.     case '.':        /* match any char..  */
  262.       store (ANY);
  263.       break;
  264.  
  265.     case '^':        /* match beginning.. */
  266.       if (p == pat)
  267.         store (BOL);
  268.       else
  269.         {
  270.           store (CHR);
  271.           store (*p);
  272.         }
  273.       break;
  274.  
  275.     case '$':        /* match endofline.. */
  276.       if (!*(p + 1))
  277.         store (EOL);
  278.       else
  279.         {
  280.           store (CHR);
  281.           store (*p);
  282.         }
  283.       break;
  284.  
  285.     case '[':        /* match char class..*/
  286.  
  287.       if (*++p == '^')
  288.         {
  289.           store (NCL);
  290.           p++;
  291.         }
  292.       else
  293.         store (CCL);
  294.  
  295.       if (*p == '-')    /* real dash */
  296.         chset (*p++);
  297.       if (*p == ']')    /* real brac */
  298.         chset (*p++);
  299.       while (*p && *p != ']')
  300.         {
  301.           if (*p == '-' && *(p + 1) && *(p + 1) != ']')
  302.         {
  303.           p++;
  304.           c1 = *(p - 2) + 1;
  305.           c2 = *p++;
  306.           while (c1 <= c2)
  307.             chset ((char) c1++);
  308.         }
  309. #ifdef EXTEND
  310.           else if (*p == '\\' && *(p + 1))
  311.         {
  312.           p++;
  313.           chset (*p++);
  314.         }
  315. #endif
  316.           else
  317.         chset (*p++);
  318.         }
  319.       if (!*p)
  320.         badpat ("Missing ]");
  321.  
  322.       for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  323.         store (bittab[n]);
  324.  
  325.       break;
  326.  
  327.     case '*':        /* match 0 or more.. */
  328.     case '+':        /* match 1 or more.. */
  329.       if (p == pat)
  330.         badpat ("Empty closure");
  331.       lp = sp;        /* previous opcode */
  332.       if (*lp == CLO)    /* equivalence..   */
  333.         break;
  334.       switch (*lp)
  335.         {
  336.  
  337.         case BOL:
  338.         case BOT:
  339.         case EOT:
  340.         case BOW:
  341.         case EOW:
  342.         case REF:
  343.           badpat ("Illegal closure");
  344.         default:
  345.           break;
  346.         }
  347.  
  348.       if (*p == '+')
  349.         for (sp = mp; lp < sp; lp++)
  350.           store (*lp);
  351.  
  352.       store (END);
  353.       store (END);
  354.       sp = mp;
  355.       while (--mp > lp)
  356.         *mp = mp[-1];
  357.       store (CLO);
  358.       mp = sp;
  359.       break;
  360.  
  361.     case '\\':        /* tags, backrefs .. */
  362.       switch (*++p)
  363.         {
  364.  
  365.         case '(':
  366.           if (tagc < MAXTAG)
  367.         {
  368.           tagstk[++tagi] = tagc;
  369.           store (BOT);
  370.           store (tagc++);
  371.         }
  372.           else
  373.         badpat ("Too many \\(\\) pairs");
  374.           break;
  375.         case ')':
  376.           if (*sp == BOT)
  377.         badpat ("Null pattern inside \\(\\)");
  378.           if (tagi > 0)
  379.         {
  380.           store (EOT);
  381.           store (tagstk[tagi--]);
  382.         }
  383.           else
  384.         badpat ("Unmatched \\)");
  385.           break;
  386.         case '<':
  387.           store (BOW);
  388.           break;
  389.         case '>':
  390.           if (*sp == BOW)
  391.         badpat ("Null pattern inside \\<\\>");
  392.           store (EOW);
  393.           break;
  394.         case '1':
  395.         case '2':
  396.         case '3':
  397.         case '4':
  398.         case '5':
  399.         case '6':
  400.         case '7':
  401.         case '8':
  402.         case '9':
  403.           n = *p - '0';
  404.           if (tagi > 0 && tagstk[tagi] == n)
  405.         badpat ("Cyclical reference");
  406.           if (tagc > n)
  407.         {
  408.           store (REF);
  409.           store (n);
  410.         }
  411.           else
  412.         badpat ("Undetermined reference");
  413.           break;
  414. #ifdef EXTEND
  415.         case 'b':
  416.           store (CHR);
  417.           store ('\b');
  418.           break;
  419.         case 'n':
  420.           store (CHR);
  421.           store ('\n');
  422.           break;
  423.         case 'f':
  424.           store (CHR);
  425.           store ('\f');
  426.           break;
  427.         case 'r':
  428.           store (CHR);
  429.           store ('\r');
  430.           break;
  431.         case 't':
  432.           store (CHR);
  433.           store ('\t');
  434.           break;
  435. #endif
  436.         default:
  437.           store (CHR);
  438.           store (*p);
  439.         }
  440.       break;
  441.  
  442.     default:        /* an ordinary char  */
  443.       store (CHR);
  444.       store (*p);
  445.       break;
  446.     }
  447.       sp = lp;
  448.     }
  449.   if (tagi > 0)
  450.     badpat ("Unmatched \\(");
  451.   store (END);
  452.   sta = OKP;
  453.   return (0);
  454. }
  455.  
  456.  
  457. static char *bol;
  458. static char *bopat[MAXTAG];
  459. static char *eopat[MAXTAG];
  460.  
  461. /*
  462.  * re_exec:
  463.  *     execute dfa to find a match.
  464.  *
  465.  *    special cases: (dfa[0])
  466.  *        BOL
  467.  *            Match only once, starting from the
  468.  *            beginning.
  469.  *        CHR
  470.  *            First locate the character without
  471.  *            calling pmatch, and if found, call
  472.  *            pmatch for the remaining string.
  473.  *        END
  474.  *            re_comp failed, poor luser did not
  475.  *            check for it. Fail fast.
  476.  *
  477.  *    If a match is found, bopat[0] and eopat[0] are set
  478.  *    to the beginning and the end of the matched fragment,
  479.  *    respectively.
  480.  *
  481.  */
  482.  
  483. int re_exec (char *lp)
  484. {
  485.   register char c;
  486.   register char *ep = 0;
  487.   register char *ap = dfa;
  488.  
  489.   bol = lp;
  490.  
  491.   bopat[0] = 0;
  492.   bopat[1] = 0;
  493.   bopat[2] = 0;
  494.   bopat[3] = 0;
  495.   bopat[4] = 0;
  496.   bopat[5] = 0;
  497.   bopat[6] = 0;
  498.   bopat[7] = 0;
  499.   bopat[8] = 0;
  500.   bopat[9] = 0;
  501.  
  502.   switch (*ap)
  503.     {
  504.  
  505.     case BOL:            /* anchored: match from BOL only */
  506.       ep = pmatch (lp, ap);
  507.       break;
  508.     case CHR:            /* ordinary char: locate it fast */
  509.       c = *(ap + 1);
  510.       while (*lp && *lp != c)
  511.     lp++;
  512.       if (!*lp)            /* if EOS, fail, else fall thru. */
  513.     return (0);
  514.     default:            /* regular matching all the way. */
  515.       while (*lp)
  516.     {
  517.       if ((ep = pmatch (lp, ap)))
  518.         break;
  519.       lp++;
  520.     }
  521.       break;
  522.     case END:            /* munged automaton. fail always */
  523.       return (0);
  524.     }
  525.   if (!ep)
  526.     return (0);
  527.  
  528.   bopat[0] = lp;
  529.   eopat[0] = ep;
  530.   return (1);
  531. }
  532.  
  533. /*
  534.  * pmatch:
  535.  *    internal routine for the hard part
  536.  *
  537.  *     This code is mostly snarfed from an early
  538.  *     grep written by David Conroy. The backref and
  539.  *     tag stuff, and various other mods are by oZ.
  540.  *
  541.  *    special cases: (dfa[n], dfa[n+1])
  542.  *        CLO ANY
  543.  *            We KNOW ".*" will match ANYTHING
  544.  *            upto the end of line. Thus, go to
  545.  *            the end of line straight, without
  546.  *            calling pmatch recursively. As in
  547.  *            the other closure cases, the remaining
  548.  *            pattern must be matched by moving
  549.  *            backwards on the string recursively,
  550.  *            to find a match for xy (x is ".*" and
  551.  *            y is the remaining pattern) where
  552.  *            the match satisfies the LONGEST match
  553.  *            for x followed by a match for y.
  554.  *        CLO CHR
  555.  *            We can again scan the string forward
  556.  *            for the single char without recursion,
  557.  *            and at the point of failure, we execute
  558.  *            the remaining dfa recursively, as
  559.  *            described above.
  560.  *
  561.  *    At the end of a successful match, bopat[n] and eopat[n]
  562.  *    are set to the beginning and end of subpatterns matched
  563.  *    by tagged expressions (n = 1 to 9).
  564.  *
  565.  */
  566.  
  567. /*
  568.  * character classification table for word boundary
  569.  * operators BOW and EOW. the reason for not using
  570.  * ctype macros is that we can let the user add into
  571.  * our own table. see re_modw. This table is not in
  572.  * the bitset form, since we may wish to extend it
  573.  * in the future for other character classifications.
  574.  *
  575.  *    TRUE for 0-9 A-Z a-z _
  576.  */
  577. static char chrtyp[MAXCHR] =
  578. {
  579.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  580.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  581.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  582.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  583.   0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
  584.   1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
  585.   0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
  586.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  587.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  588.   1, 0, 0, 0, 0, 1, 0, 1, 1, 1,
  589.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  590.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  591.   1, 1, 1, 0, 0, 0, 0, 0
  592. };
  593.  
  594. #define inascii(x)    (0177&(x))
  595. #define iswordc(x)     chrtyp[inascii(x)]
  596. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & (1<<((y)&BITIND)))
  597.  
  598. /*
  599.  * skip values for CLO XXX to skip past the closure
  600.  *
  601.  */
  602.  
  603. #define ANYSKIP    2        /* CLO ANY END ...       */
  604. #define CHRSKIP    3        /* CLO CHR chr END ...       */
  605. #define CCLSKIP 18        /* CLO CCL 16bytes END ... */
  606.  
  607. char *pmatch (char *lp, char *ap)
  608. {
  609.   register char *e;        /* extra pointer for CLO */
  610.   register char *bp;        /* beginning of subpat.. */
  611.   register char *ep;        /* ending of subpat..     */
  612.   register int op, c, n;
  613.   char *are;            /* to save the line ptr. */
  614.  
  615.   while ((op = *ap++) != END)
  616.     switch (op)
  617.       {
  618.  
  619.       case CHR:
  620.     if (*lp++ != *ap++)
  621.       return (0);
  622.     break;
  623.       case ANY:
  624.     if (!*lp++)
  625.       return (0);
  626.     break;
  627.       case CCL:
  628.     c = *lp++;
  629.     if (!isinset (ap, c))
  630.       return (0);
  631.     ap += BITBLK;
  632.     break;
  633.       case NCL:
  634.     c = *lp++;
  635.     if (isinset (ap, c))
  636.       return (0);
  637.     ap += BITBLK;
  638.     break;
  639.       case BOL:
  640.     if (lp != bol)
  641.       return (0);
  642.     break;
  643.       case EOL:
  644.     if (*lp)
  645.       return (0);
  646.     break;
  647.       case BOT:
  648.     bopat[*ap++] = lp;
  649.     break;
  650.       case EOT:
  651.     eopat[*ap++] = lp;
  652.     break;
  653.       case BOW:
  654.     if (!(lp != bol && iswordc (lp[-1])) && iswordc (*lp))
  655.       break;
  656.     return (0);
  657.       case EOW:
  658.     if ((lp != bol && iswordc (lp[-1])) && !iswordc (*lp))
  659.       break;
  660.     return (0);
  661.       case REF:
  662.     n = *ap++;
  663.     bp = bopat[n];
  664.     ep = eopat[n];
  665.     while (bp < ep)
  666.       if (*bp++ != *lp++)
  667.         return (0);
  668.     break;
  669.       case CLO:
  670.     are = lp;
  671.     switch (*ap)
  672.       {
  673.  
  674.       case ANY:
  675.         while (*lp)
  676.           lp++;
  677.         n = ANYSKIP;
  678.         break;
  679.       case CHR:
  680.         c = *(ap + 1);
  681.         while (*lp && c == *lp)
  682.           lp++;
  683.         n = CHRSKIP;
  684.         break;
  685.       case CCL:
  686.       case NCL:
  687.         while (*lp && (e = pmatch (lp, ap)))
  688.           lp = e;
  689.         n = CCLSKIP;
  690.         break;
  691.       default:
  692.         re_fail ("closure: bad dfa.", *ap);
  693.         return (0);
  694.       }
  695.  
  696.     ap += n;
  697.  
  698.     while (lp >= are)
  699.       {
  700.         if (e = pmatch (lp, ap))
  701.           return (e);
  702.         --lp;
  703.       }
  704.     return (0);
  705.       default:
  706.     re_fail ("re_exec: bad dfa.", (char) op);
  707.     return (0);
  708.       }
  709.   return (lp);
  710. }
  711.  
  712. /*
  713.  * re_modw:
  714.  *    add new characters into the word table to
  715.  *    change the re_exec's understanding of what
  716.  *    a word should look like. Note that we only
  717.  *    accept additions into the word definition.
  718.  *
  719.  *    If the string parameter is 0 or null string,
  720.  *    the table is reset back to the default, which
  721.  *    contains A-Z a-z 0-9 _. [We use the compact
  722.  *    bitset representation for the default table]
  723.  *
  724.  */
  725.  
  726. static char deftab[16] =
  727. {
  728.   0, 0, 0, 0, 0, 0, 0377, 003, 0376, 0377, 0377, 0207,
  729.   0376, 0377, 0377, 007
  730. };
  731.  
  732. void re_modw (char *s)
  733. {
  734.   register int i;
  735.  
  736.   if (!s || !*s)
  737.     {
  738.       for (i = 0; i < MAXCHR; i++)
  739.     if (!isinset (deftab, i))
  740.       iswordc (i) = 0;
  741.     }
  742.   else
  743.     while (*s)
  744.       iswordc (*s++) = 1;
  745. }
  746.  
  747. /*
  748.  * re_subs:
  749.  *    substitute the matched portions of the src in
  750.  *    dst.
  751.  *
  752.  *    &    substitute the entire matched pattern.
  753.  *
  754.  *    \digit    substitute a subpattern, with the given
  755.  *        tag number. Tags are numbered from 1 to
  756.  *        9. If the particular tagged subpattern
  757.  *        does not exist, null is substituted.
  758.  *
  759.  */
  760. int re_subs (char *src, char *dst)
  761. {
  762.   register char c;
  763.   register int pin;
  764.   register char *bp;
  765.   register char *ep;
  766.  
  767.   if (!*src || !bopat[0])
  768.     return (0);
  769.  
  770.   while (c = *src++)
  771.     {
  772.       switch (c)
  773.     {
  774.  
  775.     case '&':
  776.       pin = 0;
  777.       break;
  778.  
  779.     case '\\':
  780.       c = *src++;
  781.       if (c >= '0' && c <= '9')
  782.         {
  783.           pin = c - '0';
  784.           break;
  785.         }
  786.  
  787.     default:
  788.       *dst++ = c;
  789.       continue;
  790.     }
  791.  
  792.       if ((bp = bopat[pin]) && (ep = eopat[pin]))
  793.     {
  794.       while (*bp && bp < ep)
  795.         *dst++ = *bp++;
  796.       if (bp < ep)
  797.         return (0);
  798.     }
  799.     }
  800.   *dst = (char) 0;
  801.   return (1);
  802. }
  803.  
  804. #ifdef DEBUG
  805. /*
  806.  * symbolic - produce a symbolic dump of the
  807.  *            dfa
  808.  */
  809. symbolic (s)
  810.      char *s;
  811. {
  812.   printf ("pattern: %s\n", s);
  813.   printf ("dfacode:\n");
  814.   dfadump (dfa);
  815. }
  816.  
  817. static int dfadump (char *ap)
  818. {
  819.   register int n;
  820.  
  821.   while (*ap != END)
  822.     switch (*ap++)
  823.       {
  824.       case CLO:
  825.     printf ("CLOSURE");
  826.     dfadump (ap);
  827.     switch (*ap)
  828.       {
  829.       case CHR:
  830.         n = CHRSKIP;
  831.         break;
  832.       case ANY:
  833.         n = ANYSKIP;
  834.         break;
  835.       case CCL:
  836.       case NCL:
  837.         n = CCLSKIP;
  838.         break;
  839.       }
  840.     ap += n;
  841.     break;
  842.       case CHR:
  843.     printf ("\tCHR %c\n", *ap++);
  844.     break;
  845.       case ANY:
  846.     printf ("\tANY .\n");
  847.     break;
  848.       case BOL:
  849.     printf ("\tBOL -\n");
  850.     break;
  851.       case EOL:
  852.     printf ("\tEOL -\n");
  853.     break;
  854.       case BOT:
  855.     printf ("BOT: %d\n", *ap++);
  856.     break;
  857.       case EOT:
  858.     printf ("EOT: %d\n", *ap++);
  859.     break;
  860.       case BOW:
  861.     printf ("BOW\n");
  862.     break;
  863.       case EOW:
  864.     printf ("EOW\n");
  865.     break;
  866.       case REF:
  867.     printf ("REF: %d\n", *ap++);
  868.     break;
  869.       case CCL:
  870.     printf ("\tCCL [");
  871.     for (n = 0; n < MAXCHR; n++)
  872.       if (isinset (ap, (char) n))
  873.         printf ("%c", n);
  874.     printf ("]\n");
  875.     ap += BITBLK;
  876.     break;
  877.       case NCL:
  878.     printf ("\tNCL [");
  879.     for (n = 0; n < MAXCHR; n++)
  880.       if (isinset (ap, (char) n))
  881.         printf ("%c", n);
  882.     printf ("]\n");
  883.     ap += BITBLK;
  884.     break;
  885.       default:
  886.     printf ("bad dfa. opcode %o\n", ap[-1]);
  887.     exit (1);
  888.     break;
  889.       }
  890. }
  891.  
  892. #endif
  893.